P2149 [SDOI2009]Elaxia的路线

最短路好题，需要一定思维

题解：

首先要注意到一个性质：对于两点之间的最短路所构成的新有向图，将是一个DAG

这是很显然的，因为有环就会从终点转回起点，也就不优了

因此题目变成给出两个DAG，求他们的两条所属链，使得重合部分最大

对于样例数据，我们可以画出下面这张图，（其中蓝点是一组，红点是一组）：

于是我们可以选择其中一组点（这里选红点），从起点往终点遍历一次（红）边，注意是有向边，同时判断当前边是否是另外一个人可以同向而行（或逆向而行的边），记$f[x]$和$g[x]$，分别表示从（红色）起点到$x$路径上同向或逆向的最长相交路线长度，于是就变成了一个DAG上的DP问题，用拓扑排序解决，答案$ans=\max\{\{f\},\{g\}\}$

另外可能会有一个疑问，为什么一条边要么算在同向贡献里，要么算在逆向贡献里呢，因为一条边在所属DAG中，要么是从A到B，要么是从B到A，不然就成环了

然后再稍微提一下如何判断一条边是否在（x1->y1）或（x2->y2）的最短路径上，我们可以分别以x1,y1,x2,y2为源点跑一次最短路，若$dis_{x,y}=dis_{x,u}+dis_{v,u}$，则点$u$在(x->y)最短路径上（注意箭头是有向的）

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define x1 X
#define x2 XX
#define y1 Y
#define y2 YY

const int N=1505,M=2e4+5;
int en,h[N],dis[N][4],n,m,x1,x2,y1,y2,ans,f[N],g[N],du[N];
bool exi[M];

struct edge{
    int n,v,w;
}e[M];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

struct node{
    int x,v;
    inline bool operator < (const node &nt) const {
        return v>nt.v;
    }
};

void dij(int s,int op){ //朴素的最短路
    priority_queue<node> q;
    q.push((node){s,0});
    dis[s][op]=0;
    while(!q.empty()){
        node x=q.top();
        q.pop();
        if(dis[x.x][op]^x.v) continue;
        for(int i=h[x.x];i;i=e[i].n){
            int y=e[i].v;
            if(dis[x.x][op]+e[i].w<dis[y][op]){
                dis[y][op]=dis[x.x][op]+e[i].w;
                q.push((node){y,dis[y][op]});
            }
        }
    }
}

void topo(){
    queue<int> q;
    q.push(x1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        ans=max(ans,max(f[x],g[x])); //答案取个最大值
        for(int i=h[x];i;i=e[i].n) if(exi[i]){
            int y=e[i].v;
            if(!--du[y]) q.push(y);
            if(dis[x][2]+e[i].w+dis[y][3]==dis[y2][2]) f[y]=max(f[y],f[x]+e[i].w); //两人同向而行
            if(dis[x][3]+e[i].w+dis[y][2]==dis[y2][2]) g[y]=max(g[y],g[x]+e[i].w); //两人逆向而行
        }
    }
}

signed main(){
    read(n);read(m);read(x1);read(y1);read(x2);read(y2);
    for(int i=1,x,y,z;i<=m;i++){
        read(x);read(y);read(z);
        add(x,y,z);
        add(y,x,z);
    }
    memset(dis,60,sizeof dis);
    dij(x1,0);
    dij(y1,1);
    dij(x2,2);
    dij(y2,3);
    for(int x=1;x<=n;x++)
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(dis[x][0]+e[i].w+dis[y][1]==dis[y1][0]){
                exi[i]=1; //exi=exist 这条边是属于蓝点DAG的
                du[y]++; //入度加一
            }
        }
    topo();
    write(ans);
}
赏

fighter